package pers.qianyu.month_202011.date_20201123;

/**
 * 0 - 1 背包问题
 *
 * @author mizzle rain
 * @date 2020-11-23 15:51
 */
public class Bag {
    public int bag(int weight, int count, int[] weightArr, int[] valueArr) {
        int[][] dp = new int[count + 1][weight + 1];
        for (int i = 1; i <= count; i++) {
            for (int k = 1; k <= weight; k++) {
                if (k < weightArr[i - 1]) {
                    // 当前背包装的的量 < 要装入的量（装不下）
                    dp[i][k] = dp[i - 1][k];
                    continue;
                }
                dp[i][k] = Math.max(dp[i - 1][k],
                        dp[i - 1][k - weightArr[i - 1]] + valueArr[i - 1]);
            }
        }
        return dp[count][weight];
    }

    public static void main(String[] args) {
        int result = new Bag().bag(4, 3, new int[]{2, 1, 3}, new int[]{4, 2, 3});
        System.out.println("result = " + result);
    }
}
